//给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
//
//
//
// 示例 1：
//
//
//输入：head = [1,2,3,4,5], k = 2
//输出：[4,5,1,2,3]
//
//
// 示例 2：
//
//
//输入：head = [0,1,2], k = 4
//输出：[2,0,1]
//
//
//
//
// 提示：
//
//
// 链表中节点的数目在范围 [0, 500] 内
// -100 <= Node.val <= 100
// 0 <= k <= 2 * 10⁹
//
// Related Topics 链表 双指针 👍 639 👎 0

package leetcode.editor.cn;

import com.sicheng.algorithm.node.ListNode;

@SuppressWarnings("all")
//Java：旋转链表
public class 旋转链表 {
    public static void main(String[] args) {
        Solution solution = new 旋转链表().new Solution();
        // TO TEST
    }
//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {


        private ListNode tail;

        public ListNode rotateRight(ListNode head, int k) {

            if (head == null)
                return null;
            if (head.next == null)
                return head;
            short size = getSize(head);
            if (k >= size) {
                k = k % size;
            }
            if (k == 0)
                return head;

            //将倒数第k个结点 移到头部
            //寻找倒数第（k+1）个结点
            //即寻找正数 (size-k)个结点

            short count = 1;
            ListNode temp = head;
            while (count < (size - k)) {
                count++;
                temp = temp.next;
            }

            tail.next = head;
            head = temp.next;
            temp.next = null;
            return head;

        }

        public short getSize(ListNode head) {
            if (head == null)
                return 0;
            short size = 1;


            while (head.next != null) {
                size++;
                head = head.next;
            }

            tail = head;
            return size;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}
